package hdu6375;
/*
hdu6375，1p80，码蹄集DB201808
输入：
2 10
1 1 1 23
1 1 0 233
2 1 1 
1 2 1 2333
1 2 1 23333
3 1 2 1
2 2 0
2 1 1
2 1 0
2 1 1
输出：
23
-1
2333
233
23333
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
public class Main {

	public static void main(String[] args) throws IOException {
		//输入优化
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		
		//读取第一行
		String[] lineArr = read.readLine().split(" ");
		
		int n = Integer.parseInt(lineArr[0]);
		int m = Integer.parseInt(lineArr[1]);
		
		//声明并初始化双向队列数组
		Deque<Integer>[] deque = new Deque[n+1];
		
		for(int i=0;i<=n+1;i++) {
			deque[i] = new LinkedList<Integer>();
		}
		
		while(m-->0) {//m大于0时继续，m自身减1
			//读取下一行
			lineArr = read.readLine().split(" ");
			//第一个数k，表示操作
			int k = Integer.parseInt(lineArr[0]);
			//声明变量对应输入参数
			int u,val,w,v;
			switch(k) {
				case 1:
					
					u = Integer.parseInt(lineArr[1]);
					w = Integer.parseInt(lineArr[2]);
					val = Integer.parseInt(lineArr[3]);
					if(w==0) {
						//val加在u队列前面
						deque[u].addFirst(val);
					}

					if(w==1){
						deque[u].addLast(val);
					}
					break;
				case 2:
					
					u = Integer.parseInt(lineArr[1]);
					w = Integer.parseInt(lineArr[2]);
					if(deque[u].isEmpty()) {
						//队列为空，输出-1
						System.out.println(-1);
					}else {
						if(w==0) {
							//输出第一项
							System.out.println(deque[u].pollFirst());
						}
						if(w==1){
							//输出最后一项
							System.out.println(deque[u].pollLast());
						}
					}
					break;
				case 3:
					
					u = Integer.parseInt(lineArr[1]);
					v = Integer.parseInt(lineArr[2]);
					w = Integer.parseInt(lineArr[3]);
					if(w==0) {
						//v队列顺序接在u队列后面
						deque[u].addAll(deque[v]);
						
					}
					if(w==1) {
						//v队列逆序接在u队列后面
						while(!deque[v].isEmpty()) {
							deque[u].add(deque[v].pollLast());
						}
					}
					//清空v队列
					deque[v].clear();
					break;
			}
		}
		
	}

}
